package alo.p6.work4;

import alo.p6.BinaryTreeNode;

/**
 * @ClassName IsBST
 * @Description 判断一个树是否为二叉搜索树
 * @Author Fanxc
 * @DATE 2021/2/15 9:55
 * @Version 1.0
 */
public class IsBST {
    BinaryTreeNode findMax(BinaryTreeNode root){
        if (root==null){
            return null;
        }else if (root.getRight()==null){
            return root;
        }else {
            return findMax(root.getRight());
        }
    }

    BinaryTreeNode findMin(BinaryTreeNode root){
        if (root==null){
            return null;
        }else if (root.getLeft()==null){
            return root;
        }else {
            return findMin(root.getLeft());
        }
    }
    //这个方法是错误的，只检查数值对于当前结点的大小比较
    boolean isBST(BinaryTreeNode root){
        if (root==null){
            return true;
        }
        if (root.getLeft()!=null&&root.getLeft().getData()> root.getData()){
            return false;
        }
        if (root.getRight()!=null&&root.getRight().getData()< root.getData()){
            return false;
        }
        return isBST(root.getLeft()) && isBST(root.getRight());
    }


    //左子树中的最大元素需要小于当前结点，右子树同理
    boolean isBST2(BinaryTreeNode root){
        if (root==null){
            return true;
        }
        if (root.getLeft()!=null&&findMax(root.getLeft()).getData()> root.getData()){
            return false;
        }
        if (root.getRight()!=null&&findMin(root.getRight()).getData()< root.getData()){
            return false;
        }
        return isBST2(root.getLeft()) && isBST(root.getRight());
    }

    //根据范围往下递归判定，初始min和max为Integer.MIN_VALUE和Integer.MAX_VALUE
//    int min=Integer.MIN_VALUE;
//    int max=Integer.MAX_VALUE;
    boolean isBST3(BinaryTreeNode root,int min,int max){
        if (root==null){
            return true;
        }
        return root.getData()>min&&root.getData()<max&&
                isBST3(root.getLeft(),min,root.getData())&&
                isBST3(root.getRight(), root.getData(), max);
    }

    //全部结点值的先后顺序是中序遍历的顺序，不断将访问结点值与前面访问结点值进行比较，以此判断是否为BST
//    int prev=Integer.MIN_VALUE;
    boolean isBST4(BinaryTreeNode root,int prev){
        if (root==null){
            return true;
        }
        if (!isBST4(root.getLeft(),prev)){
            return false;
        }
        if (root.getData()<prev){
            return false;
        }
        prev=root.getData();
        return isBST4(root.getRight(),prev);
    }


}
